package Year22_Month05.day25;

import java.util.Arrays;

public class 快速排序2 {
    public static void quickSort(int[] arr,int left,int right){
        if(right - left > 1){
            int index = partion2(arr,left,right);
            quickSort(arr,left,index);
            quickSort(arr,index+1,right);
        }
    }

    public static int partion2(int[] arr,int left,int right){
        //当前版本为挖坑法
        //老规矩，还是先定义当前比较值的下标
        int index = right - 1;
        //然后是设置一系列的需要属性
        int key = arr[index];
        int begin = left;
        int end = index;
        while(begin < end){
            //先从前往后找第一个大于key的值
            while(begin < end && arr[begin] <= key){
                begin++;
            }
            if(begin < end){
                arr[end] = arr[begin];
            }
            //再从后往前找第一个小于key的
            while(begin < end && arr[end] >= key){
                end--;
            }
            if(begin < end){
                arr[begin] = arr[end];
            }
        }
        arr[begin] = key;
        return begin;
    }

    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        quickSort(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));
    }
}
